//
//  UIViewController+Mian.swift
//  CodeList
//
//  Created by 山神 on 2021/9/6.
//

import UIKit

extension UIViewController {

    //数组合并
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        nums1.removeLast(n)
        nums1.append(contentsOf: nums2)
        nums1.sort()
    }

    func sortColors(_ nums: inout [Int]) {
        var p0 = 0
        var p2 = nums.count - 1
        var i = 0
        while (i <= p2) {
            if nums[i] == 0 {
                (nums[i], nums[p0]) = (nums[p0], nums[i])
                i += 1
                p0 += 1
            } else if nums[i] == 1 {
                i += 1
            } else {
                nums.swapAt(p2, i)
                p2 -= 1
            }
        }
    }
}

//    冒泡排序
extension ViewController {
    // 冒泡排序 优化二（内层优化）
    func bubbleSort2(nums: inout [Int]) {
        let n = nums.count
        var endIndex = 0 // swap变量用来标记循环里最后一次交换的位置
        var k = n - 1 // 内循环判断条件
        for _ in 0 ..< n {
            var isSort = true
            for j in 0 ..< k {
                if nums[j] > nums[j + 1] {
                    nums.swapAt(j, j + 1)
                    isSort = false
                    endIndex = j
                }
            }
            k = endIndex
            if isSort { break }
        }
    }
    // 选择排序: 找出最小的和第一个交换
    func selectionSort(unsortedArray: inout [Int]) {
        guard !unsortedArray.isEmpty else { return }
        for i in 0 ..< unsortedArray.count {
            var minIndex = i
            for j in i+1 ..< unsortedArray.count {
                if unsortedArray[j] < unsortedArray[minIndex] {
                    minIndex = j
                }
            }
            if minIndex != i {
                unsortedArray.swapAt(i, minIndex)
            }
        }
    }
    //插入排序: 打扑克
    func insertionSort(array:inout [Int]) {
        for x in 1 ..< array.count {
            var y = x
            while y > 0 && array[y] < array[y - 1] {
                array.swapAt(y - 1, y)
                y -= 1
            }
        }
    }
    //希尔排序
}

// 判断这个链表是不是循环列表
class Node {
    public var next: Node?
    init() {}
}

extension UIViewController {
    func hasCycle(head: Node?) -> Bool {
        if head == nil || head?.next == nil { return false }
        var slow = head
        var fast = head?.next

        while fast != nil && fast?.next != nil {
            if slow === fast { return true }
            slow = slow?.next
            fast = fast?.next?.next
        }
        return false
    }
}

// 剑指offer的算法
//func searchInsert(_ nums: [Int], _ target: Int) -> Int {
//    
//}
